package com.gorkr.offer;

import org.junit.jupiter.api.Test;

/**
 * 机器人的运动范围
 * @author gorkr
 * @date 2022/07/26 21:19
 **/
public class M13JiQiRenDeYunDongFanWeiIcof {

    private int res = 0;

    public int movingCount(int m, int n, int k) {

//        boolean[][] flag = new boolean[m][n];
        boolean[][] visited = new boolean[m][n];
        traverse(0,0,k,m,n,visited);
        return res;
    }

    private void traverse(int i, int j, int k,int m ,int n,boolean[][] visited){
        if(visited[i][j]){
            return;
        }
        visited[i][j] = true;
        if(sum(i,j)>k){
            return;
        }
        if(i+1<=m-1){
            traverse(i+1,j,k,m,n,visited);
        }
        if(j+1<=n-1){
            traverse(i,j+1,k,m,n,visited);
        }
        res++;
    }


    private int sum(int m, int n){
        int sum = 0;
        for (;m>0;m/=10){
            sum +=m%10;
        }
        for (;n>0;n/=10){
            sum +=n%10;
        }
        return sum;
    }

    @Test
    public void test(){
        System.out.println(movingCount(4, 4, 5));
    }


}
    